Arrays¶

  • Why are arrays so popular?

Arrays¶

  • Why are arrays so popular?

    • Given any index $i$, we can access $A[i]$ quickly (in constant time)
  • How do you think they are typically implemented?

Arrays¶

  • Given any index $i$, we can access $A[i]$ quickly (in constant time)

  • Usually implemented as contiguous locations in memory

image.png

Time complexities of the operations?¶

  • insert at index

  • delete

  • search

  • insert at the beginning

  • insert at the end

image.png

  • static: size does not change at runtime

  • dynamic: size may change at runtime

Linked Lists¶

image.png

In [2]:
class ListNode :
    def __init__(self, data) :
        self.data = data
        self.next = None

Linked List¶

  • A singly linked list
    • Each node contains a single link field
    • allows for a complete traversal from a distinctive first node to the last.
  • a = ListNode(11)
  • b = ListNode(52)
  • c = ListNode(18)

image.png

Please pay attention to how the boxes and arrows are drawn!¶

In [3]:
a = ListNode(11)
b = ListNode(52)
c = ListNode(20)

print(a.data)
print(b.data)
print(c.data)
11
52
20
In [4]:
a.next = b
b.next = c
  • a.next = b
  • b.next = c

image.png

In [4]:
# Print elements in the list

# print(a) 
# while a != None:
#     print (a.data, end=" ")
#     a = a.next

tmp = a
while tmp != None:
    print (tmp.data, end=" ")
    tmp = tmp.next
11 52 20 
In [5]:
#print(a.data)#11
#print(a.next.data)#18 
#print(a.next.next.data)#318 


head = a 
#print(head.next.next.next.data)

tmp = head
lookingfor = 18

if (tmp != None):
    if tmp.data == lookingfor:
        print(tmp.data)
    else:
        while(tmp.next != None) and (tmp.next.data != lookingfor):
            tmp = tmp.next 

        if tmp.next != None:
            print(tmp.next.data) 
        else:
            print("not found")
else:
    print("list empty") 
    
# next, do the actual insert
not found
In [7]:
# Search through the elements

head = a # the head points to the first elem in the list


lookingfor = 20
flgfound = False

curr = head # begin at the beginning

while curr != None:
    if (curr.data == lookingfor): # check for the content (data)
        print("found what you are looking for! :-)")
        flgfound = True
        break
    curr = curr.next # move to the next node 
    
if (flgfound == False):
    print("could not find it :-(")
        
found what you are looking for! :-)
In [8]:
# Search through the elements without the flag

head = a # the head points to the first elem in the list

lookingfor = 20

curr = head # begin at the beginning

while curr != None:
    if (curr.data == lookingfor): # check for the content (data)
        print("found what you are looking for! :-)")
        break
    curr = curr.next # move to the next node 
    
if (curr == None):
    print("could not find it :-(")
        
found what you are looking for! :-)
In [ ]:
class ComplicatedNode :
    def __init__(self, data) :
        self.data = data
        self.left = None
        self.right = None
        self.third = None
        self.fourth = None
In [ ]:
ca = ComplicatedNode(10)
cb = ComplicatedNode(20)
cc = ComplicatedNode(30)
In [ ]:
ca.left = cb
ca.right = cc 
print(ca.left.data)
print(ca.right.data)

What is the time complexity of searching a linked list?¶

What is the time complexity of searching an array?¶

image.png

Insert a node (96) between 18 and 36¶

image-3.png

Insert a node (96) between 18 and 36¶

image-3.png

image-5.png

image.png

image.png

  1. Find 18

  2. Copy 18's next to 96's next

    • 96's next will point to 36
  3. Point 18's next to 96

    • 18's next will point to 96

We are done!

What happens if we do 3 before 2 above?¶
  1. Point 18's next to 96

    • 18's next will point to 96
  2. Point 18's next to 96's next

Remove a node from a list¶

image.png

Remove a node from a list¶

image-2.png

It makes matters easier to have a predecessor¶

image.png

In [ ]:
head = a  # head always points to the first element of the list

rmval = 18
curr = head
prev = None

while curr != None:
    if curr.data == rmval:
        if prev == None: # first guy in the list
            head = head.next
        else: 
            prev.next = curr.next
        break
    prev = curr
    curr = curr.next

tmp = head
while tmp != None:
    print(tmp.data,end=" ")
    tmp = tmp.next
print("")

Time complexities of the operations?¶

  • insert

  • delete

  • search

  • insert at the beginning

  • insert at the end

Append to the end of a list¶

  • The same algorithm that works for insert will work for append ("insert at the end")

  • Suppose this operation needs to happen frequently.

image.png

Append to the end of a list¶

  • This is happening often, taking $O(n)$ time, each time... image-3.png

  • Any ideas?

image.png

Let's use a tail !¶

What are the advantages of using a tail?¶

  • Just one extra variable

  • Independent of $n$ - the length of the list

  • Makes append a constant time operation!!

image.png

Doubly-linked Lists¶

image.png

In [1]:
class DListNode :
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None
In [2]:
a = DListNode(21)
b = DListNode(57)
c = DListNode(38)
d = DListNode(14)

a.next = b
b.prev = a

b.next = c
c.prev = b

c.next = d
d.prev = c

head = a 
tail = d
In [3]:
curr = head

print("forward:")
while curr != None:
    print(curr.data,end=" ")
    curr = curr.next
    
print("\nbackward:")
curr = tail
while curr != None:
    print(curr.data,end=" ")
    curr = curr.prev
forward:
21 57 38 14 
backward:
14 38 57 21 

Add a node to a doubly linked list¶

image.png

In [4]:
def dllprintf(dll):
    curr = head
    while curr != None:
        print(curr.data,end =" ")
        curr = curr.next
    print("")
In [5]:
def dllprintb(dll):
    curr = tail
    while curr != None:
        print(curr.data,end =" ")
        curr = curr.prev
    print("")
In [6]:
# The current list contains 
dllprintf(head)

# Add it between the second and third nodes
second = head.next
third = second.next

newnode = DListNode(46)

print("\nadding the newnode between the 2nd and 3rd elements")
newnode.next = third
newnode.prev = second

second.next = newnode
third.prev  = newnode

dllprintf(head)
dllprintb(tail)
21 57 38 14 

adding the newnode between the 2nd and 3rd elements
21 57 46 38 14 
14 38 46 57 21 

Homework :-P¶

  • Add a node at the beginning of a doubly linked list

  • Add a node at the end of a doubly linked list

Circular Linked Lists¶

image.png

  • Used in operating systems to serve jobs in round-robin fashion (CPU scheduling)

Circular Linked Lists¶

image.png

  • Singly Linked Circular List

image-2.png

  • Doubly Linked Circular List

Matrices ("may-tree-ceez")¶

  • singular matrix pronounced "may-tricks"
    • pronounciation often confused with metrics "me(short)-tricks"

2D Arrays¶

image-2.png

2D Arrays¶

image.png

  • An array of arrays
In [7]:
# Implementation of the Array2D ADT using an array of arrays.

class Array2D : # Creates a 2-D array of size numRows x numCols.

    def __init__( self, numRows, numCols ):
        # Create a 1-D array to store an array reference for each row.
        self._Rows = [0]*( numRows )
        
        # Create the 1-D arrays for each row of the 2-D array. 
        for i in range( numRows ) :
            self._Rows[i] = [i]*( numCols )


    # Returns the number of rows in the 2D array
    def numRows( self ):
        return len( self._Rows )

    # Returns the number of columns in the 2D array
    def numCols( self ):
        return len( self._Rows[0] )

    # Prints the entire array
    def prn2d( self ):
        for i in range( len(self._Rows )):
            for j in range( len(self._Rows[0]) ):
                print(self._Rows[i][j],end=" ")
            print("")
        return("")
    
    def setrow( self, rowNum, contents ):
        for j in range( len(self._Rows[0])):
            self._Rows[rowNum][j] = contents[j]
In [8]:
a2 = Array2D(4, 6)
In [9]:
print("No. of rows: ",a2.numRows())
print("No. of cols: ",a2.numCols())
print(a2.prn2d())
No. of rows:  4
No. of cols:  6
0 0 0 0 0 0 
1 1 1 1 1 1 
2 2 2 2 2 2 
3 3 3 3 3 3 

In [10]:
mycon0 = [".",".","-","-",".","."]
mycon1 = [".",".","0","0",".","."]
mycon2 = [".",".","^","^",".","."]
mycon3 = [".","\\","-","-","/","."]
a2.setrow(0,mycon0)
a2.setrow(1,mycon1)
a2.setrow(2,mycon2)
a2.setrow(3,mycon3)
print(a2.prn2d())
. . - - . . 
. . 0 0 . . 
. . ^ ^ . . 
. \ - - / . 

The Game of Life¶

image-2.png

  • Birth rule: An empty, or “dead,” cell with precisely three “live” neighbours (full cells) becomes live.

  • Death rule: A live cell with zero or one neighbours dies of isolation; a live cell with four or more neighbours dies of overcrowding.

  • Survival rule: A live cell with two or three neighbours remains alive

(https://www.nytimes.com/2020/12/28/science/math-conway-game-of-life.html)

  • Birth rule: An empty, or “dead,” cell with precisely three “live” neighbours (full cells) becomes live.

  • Death rule: A live cell with zero or one neighbours dies of isolation; a live cell with four or more neighbours dies of overcrowding.

  • Survival rule: A live cell with two or three neighbours remains alive

(https://www.nytimes.com/2020/12/28/science/math-conway-game-of-life.html)

https://playgameoflife.com

image-2.png

John Horton Conway, investigating “Life” in 1974.¶

(Credits: Kelvin Brodie/The Sun News Syndication)

The Game of Life¶

  • Complex patterns from simple rules

  • An example of a "cellular automaton"

  • Formal model of a computer

Implement Matrix Operations using 2D Arrays¶

  • Add a matrix to this one.

  • Subtract a matrix from this one.

  • Multiply a matrix with this one.

  • Transpose this matrix

Matrix Addition and Subtraction¶

image.png

Matrix Scaling¶

image.png

Matrix Multiplication¶

image.png

Matrix Multiplication¶

image.png

image-2.png

Matrix Transpose¶

image.png

In [31]:
# Implementation of the Array2D ADT using an array of arrays.

class Array2D : # Creates a 2-D array of size numRows x numCols.

    def __init__( self, numRows, numCols ):
        # Create a 1-D array to store an array reference for each row.
        self._Rows = [0]*( numRows )
        
        # Create the 1-D arrays for each row of the 2-D array. 
        for i in range( numRows ) :
            self._Rows[i] = [i]*( numCols )


    # Returns the number of rows in the 2D array
    def numRows( self ):
        return len( self._Rows )

    # Returns the number of columns in the 2D array
    def numCols( self ):
        return len( self._Rows[0] )

    # Prints the entire array
    def prn2d( self ):
        for i in range( len(self._Rows )):
            for j in range( len(self._Rows[0]) ):
                print(self._Rows[i][j],end=" ")
            print("")
        #return()
    
    def setrow( self, rowNum, contents ):
        for j in range( len(self._Rows[0])):
            self._Rows[rowNum][j] = contents[j]
In [ ]:
mya = Array2D(2,4)
mya.prn2d()

Implementation of Matrix operations¶

  • In Python and Java, you can define classes
    • The "matrix" class can use the "Array2D" class
      • Each one of the matrix operations: add, subtract, multiply etc. will become methods

      • A "function" defined inside a class is called a "method"

      • An "object" (variable) M1 of "class" (type) Array2D can "invoke" (call) a "method" (function) "prn2D" using the "." operator.

        mya = Array2D(2,4)

        mya.prn2d( )

# Implementation of the Matrix ADT using a 2-D array.¶

from array import Array2D

class Matrix :

# Creates a matrix of size numRows x numCols initialized to 0.
def __init__( self, numRows, numCols ): 
    self._theGrid = Array2D ( numRows, numCols ) 
    
Implementation of the Matrix ADT using a 2-D array.¶
Example of inheritance¶

class Matrix (Array2D):

# Creates a matrix of size numRows x numCols initialized to 0.
def __init__( self, numRows, numCols ): 
    Array2D.__init__(self, numRows, numCols)
    
# Returns the number of rows in the 2D array
def numRows( self ):
return super().numRows()

# Returns the number of columns in the 2D array
def numCols( self ):
    return Array2D.numCols()

# Prints the entire array
def prn2d( self ):
    return super().prn2d( )
In [32]:
# Implementation of the Matrix ADT using a 2-D array.
# Example of inheritance

class Matrix (Array2D):
    # Creates a matrix of size numRows x numCols initialized to 0.
    def __init__( self, numRows, numCols ): 
        Array2D.__init__(self, numRows, numCols)
        
    # Returns the number of rows in the 2D array
    def numRows( self ):
        return super().numRows()

    # Returns the number of columns in the 2D array
    def numCols( self ):
        return Array2D.numCols()

    # Prints the entire array
    def prn2d( self ):
        return super().prn2d( )
In [33]:
M = Matrix(3,5)
M.numRows()
M.prn2d()
0 0 0 0 0 
1 1 1 1 1 
2 2 2 2 2 

Sparse Matrix¶

  • A matrix containing a large number of zeros

  • Where?

    • Very common in scientific applications, as in systems of linear equations. image.png

image.png

Sparse Matrix¶

  • Where else?

  • Suppose I build a graph of "who-knows-whom" in Ahmedabad University

    folks-in-DS | rest-of-the-folks -------------------|----------------------------------------------- 1 1 1 1 0 1 1 1 0 | 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 1 0 1 1 | 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0

Ok, so what's the fuss about?¶

  • If we implement this as a 2D array,....?

image.png

Sparse Matrix¶

  • What can we do instead?

image.png

image-3.png

image-4.png

The story so far...¶

  • Recursion

    • Mathematical
    • Programming
    • Problems with both types of solutions: recursive and iterative
    • Efficiency
  • Algorithm Analysis

    • "count steps" instead of timing programs (time-complexity)
    • "rough upper bound" of time-complexity $\longrightarrow$ big-Oh notation
    • $O(n), O(\log n), O(n^2)...$

The story so far...¶

  • Linear Data Structures
    • Arrays
    • Linked Lists
    • Time complexity of basic operations
    • Comparisons